Лемма о нелинейной функции

Пусть $f \notin L$. Тогда конъюнкцию можно задать формулой над множеством $\{f, 0, 1, \neg\}$.

Пусть $h(x_{1}, \dots, x_{k})$ — полином Жегалкина нелинейной функции $f$. В нем есть нелинейный одночлен; не ограничивая общности, считаем, что он содержит $x_{1} x_{2}$. Разложим $h$ по этим переменным: $$h(x_{1}, \dots, x_{k}) = x_{1} x_{2} f_{1}(x_{3}, \dots, x_{k}) + x_{1} f_{2} + x_{2} f_{3} + f_{4}$$ Поскольку $f_{1} \not\equiv 0$, зафиксируем константы $c_{3}, \dots, c_{k}$ так, чтобы $f_{1}(c_{3}, \dots, c_{k}) = 1$. Тогда функция от двух переменных $\psi(x_{1}, x_{2}) = f(x_{1}, x_{2}, c_{3}, \dots, c_{k})$ примет вид: $$\psi(x_{1}, x_{2}) = x_{1} x_{2} + \alpha x_{1} + \beta x_{2} + \gamma$$ где $\alpha, \beta, \gamma$ — значения соответствующих полиномов на наборе констант. Положим $\phi(x_{1}, x_{2}) = \psi(x_{1} + \beta, x_{2} + \alpha) + \alpha\beta + \gamma$. Раскрывая скобки и учитывая арифметику по модулю 2, получаем: $$\phi(x_{1}, x_{2}) = (x_{1} + \beta)(x_{2} + \alpha) + \alpha(x_{1} + \beta) + \beta(x_{2} + \alpha) + \gamma + \alpha\beta + \gamma = x_{1} x_{2}$$ Так как прибавление 1 по модулю 2 соответствует отрицанию ($x+1 = \bar{x}$), мы выразили конъюнкцию через исходную функцию, константы и, возможно, отрицание. $\square$